package com.hardy.leecode;

/**
 * Author: Hardy
 * Date:   2021/1/8
 * Description:
 **/
public class Que60 {
    public static void main(String[] args) {
        System.out.println(new Solution().getPermutation(3, 3));
    }

    static class Solution {
        public String getPermutation(int n, int k) {
            // 划分
            int[] a = new int[n + 1];
            int[] b = new int[n + 1];
            b[0] = 1;

            for (int i = 1; i <= n; i++) {
                a[i] = i;
                b[i] = b[i - 1] * i;
            }


            StringBuilder sb = new StringBuilder();

            // 1.查找首数字 2.余数=0 > 从小到大
            cul(sb, a, b, 1, n, k);

            return sb.toString();
        }

        public void cul(StringBuilder sb, int[] a, int[] b, int i, int n, int k) {
            if (sb.length() == n) return;

            // 计算当前位置数字
            int t = k / b[n - i];
            int d = k % b[n - i];

            //
            int val = search(a, d == 0 ? t : t + 1);
            sb.append(val);

            if (d == 0) {
                for (int j = n; sb.length() < n; j--) {
                    if (a[j] == -1) continue;
                    sb.append(j);
                }
            } else {
                cul(sb, a, b, i + 1, n, d);
            }
        }

        public int search(int[] a, int i) {
            int c = 0;
            for (int j = 1; j < a.length; j++) {
                if (a[j] == -1) continue;

                if (++c == i) {
                    a[j] = -1;
                    return j;
                }
            }
            return 0;
        }
    }
}
